Placement remains a critical step in the RTL to GDS II or equivalents synthesis process. The exponential growth of complexity in integrated circuits designs has dramatically increased the demand for better optimization of the placement algorithms. Recent development of placement algorithms often ignores an important feature of all placement techniques—stability and thus leads to undesired waste of computation resources.
A placement tool is considered to offer stability if, for two starting designs which exhibit only small differences between them, the resulting final designs also have small or limited differences. That is, a small change in the input design results in a small change in the final output. For example, stability is important for an incremental design flow where a circuit designer who introduces small changes to a design will want to obtain a new placement incorporating those changes but with minimal effect on the unchanged portions of the design. Placement tools with good stability may also prevent undesired waste of computational resources and runtime that may increase the cost of the design as well as delay the intended time to market.
There are several existing approaches to address the overall placement problem, yet none of which have emphasized placement stability. Some of these approaches start by computing an initial placement, which may not be feasible in that many gates overlap each other. This initial placement is then modified so as to remove the overlaps between the gates. Typical placement tools tend to iteratively and incrementally remove a fraction of the overlaps at a time until the overlaps are reduced to an extent so the detailed placement tool can determine a completely legal and non-overlapping layout.
Existing approaches to remove overlaps from an initial placement have several drawbacks. For example, one approach is to use partitioning techniques, such as minimum-cut partitioning, in a divide-and-conquer fashion to split the die into smaller regions. The netlist is also divided among the subregions of the die so that each subregion represents a smaller spreading sub-problem which can be solved more easily, perhaps through recursive application of partitioning. Such techniques have a drawback in that small changes to the starting netlist may result in large changes to the final result. Such instability leads to relatively unpredictable performance of such algorithms.
Another approach to gate spreading is the so-called force-directed method. In algorithms adopting the force-directed method, the overlaps between the gates are used to generate repulsive forces which push the gates away from the areas of overlap. This key drawback to this approach is that it is difficult to determine a suitable magnitude of force necessary to resolve any particular overlap which can lead to excessive computational complexity and runtime of the algorithm.
A recently proposed approach to gate spreading is the grid-warping technique as first published by Large-Scale Placement by Grid-Warping by Z. Xiu, J. D. Ma, S. M. Fowler, and R. A. Rutenbar, Design Automation Conference 2004. The grid-warping technique relies on transforming small slicing structures to a regular grid using non-linear programming solver. The disadvantage of grid-warping algorithms is the relatively high computational cost and runtime involved. Moreover, the grid-warping algorithms optimize the placement solely for netlength minimization rather than for stability optimization.
Thus, a need exists for computing a spread of objects over an area such that the final locations of the objects are relatively uniformly spread over the entire area by grid morphing and such that the final locations of the objects are minimally perturbed from their initial starting locations and therefore minimizing the perturbation to the placement of the design features and thus maintaining the stability of the placement.
The present invention transforms a grid superposed on the placement area to another grid and subsequently re-computes the locations of the gates based on that transformation. One of the advantages of the grid morphing technique is that the computation for the new locations of the gates can be done more quickly. Another advantage of the grid morphing technique is the minimal or even no overlapping due to smoothly moving cells while preserving the relative positions of the cells during the grid morphing process to spread the gates. Moreover, some embodiments of the invention may incorporate various characteristics of the design in the grid morphing objective functions and/or the solver without significant increase in runtime overhead.